{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Binary String After Change"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumBinaryString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #修改后的最大二进制字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制字符串 <code>binary</code> ，它仅有 <code>0</code> 或者 <code>1</code> 组成。你可以使用下面的操作任意次对它进行修改：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>操作 1 ：如果二进制串包含子字符串 <code>\"00\"</code> ，你可以用 <code>\"10\"</code> 将其替换。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>比方说， <code>\"<strong>00</strong>010\" -> \"<strong>10</strong>010\"</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>操作 2 ：如果二进制串包含子字符串 <code>\"10\"</code> ，你可以用 <code>\"01\"</code> 将其替换。\n",
    "\t<ul>\n",
    "\t\t<li>比方说， <code>\"000<strong>10</strong>\" -> \"000<strong>01</strong>\"</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回执行上述操作任意次以后能得到的 <strong>最大二进制字符串</strong> 。如果二进制字符串 <code>x</code> 对应的十进制数字大于二进制字符串 <code>y</code> 对应的十进制数字，那么我们称二进制字符串<em> </em><code>x</code><em> </em>大于二进制字符串<em> </em><code>y</code><em> </em>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>binary = \"000110\"\n",
    "<b>输出：</b>\"111011\"\n",
    "<b>解释：</b>一个可行的转换为：\n",
    "\"0001<strong>10</strong>\" -> \"0001<strong>01</strong>\" \n",
    "\"<strong>00</strong>0101\" -> \"<strong>10</strong>0101\" \n",
    "\"1<strong>00</strong>101\" -> \"1<strong>10</strong>101\" \n",
    "\"110<strong>10</strong>1\" -> \"110<strong>01</strong>1\" \n",
    "\"11<strong>00</strong>11\" -> \"11<strong>10</strong>11\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>binary = \"01\"\n",
    "<b>输出：</b>\"01\"\n",
    "<b>解释：</b>\"01\" 没办法进行任何转换。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= binary.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>binary</code> 仅包含 <code>'0'</code> 和 <code>'1'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-binary-string-after-change](https://leetcode.cn/problems/maximum-binary-string-after-change/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-binary-string-after-change](https://leetcode.cn/problems/maximum-binary-string-after-change/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"000110\"', '\"01\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        if '0' not in binary:\n",
    "            return binary\n",
    "        ind = binary.index('0')\n",
    "        cnt = Counter(binary[ind:])\n",
    "        return '1' * (ind + max(0, cnt['0']-1)) + ('0' if cnt['0'] > 0 else '') + '1' * cnt['1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maximumBinaryString(self, binary: str) -> str:\n",
    "#         if '0' not in binary:\n",
    "#             return binary\n",
    "#         t=binary.index('0')\n",
    "#         cnt=binary[t:].count('1')\n",
    "#         return '1'*(len(binary)-cnt-1)+'0'+'1'*cnt\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        # b = list(binary)\n",
    "        n = len(binary)\n",
    "        high1 = 0\n",
    "        for i in range(n):\n",
    "            if binary[i] == '0':\n",
    "                break\n",
    "            high1 += 1\n",
    "            # print(high1)\n",
    "        s = collections.Counter(binary)\n",
    "        if s['0'] == 0:\n",
    "            return binary\n",
    "        end1 = s['1'] - high1\n",
    "        first1 = n - end1 - 1\n",
    "        ans = '1' * first1+ '0' + '1' * end1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        if len(binary) == 1:\n",
    "            return binary\n",
    "        cont1pos = 0\n",
    "        while binary[cont1pos] == \"1\":\n",
    "            cont1pos += 1\n",
    "            if cont1pos >= len(binary):\n",
    "                return binary\n",
    "        \n",
    "        cnt1 = 0\n",
    "        for i in range(cont1pos, len(binary)):\n",
    "            if binary[i] == \"1\":\n",
    "                cnt1 += 1\n",
    "        \n",
    "        return \"1\" * (len(binary) - cnt1 - 1) + \"0\" * 1 + \"1\" * cnt1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        if '0' not in binary:\n",
    "            return binary\n",
    "        t=binary.index('0')\n",
    "        cnt=binary[t:].count('1')\n",
    "        return '1'*(len(binary)-cnt-1)+'0'+'1'*cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        one_num = 0\n",
    "        zero_num = 0\n",
    "        front_one_num = 0\n",
    "        flag = True\n",
    "        for c in binary:\n",
    "            if c == '1':\n",
    "                if flag:\n",
    "                    front_one_num += 1\n",
    "                else:\n",
    "                    one_num += 1\n",
    "            else:\n",
    "                flag = False\n",
    "                zero_num += 1\n",
    "\n",
    "        if zero_num == 0:\n",
    "            return \"1\" * front_one_num\n",
    "        elif zero_num == 1:\n",
    "            return binary\n",
    "\n",
    "        ans = \"1\" * (front_one_num + zero_num - 1) + \"0\" + \"1\" * one_num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumBinaryString(self, binary: str) -> str:\r\n",
    "        left, n = 0, len(binary)\r\n",
    "        for b in binary:\r\n",
    "            if b == '1':\r\n",
    "                left += 1\r\n",
    "            else: break\r\n",
    "        if left == n: return binary\r\n",
    "        cnt = binary[left + 1:].count('1')\r\n",
    "        return '1' * (n - cnt - 1) + '0' + '1' * cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n=len(binary)\n",
    "        if binary.count('0')==0:return binary\n",
    "        pre1=binary.index('0')\n",
    "        count0=binary.count('0')\n",
    "        if count0:\n",
    "            ans=pre1*'1'+'1'*(count0-1)+'0'+'1'*(binary.count('1')-pre1)\n",
    "            return ans\n",
    "\n",
    "        else:return binary\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maximumBinaryString(self, binary: str) -> str:\n",
    "#         zero_count = 0\n",
    "#         for i in range(len(binary)):\n",
    "#             if binary[i] == '0':\n",
    "#                 zero_count += 1\n",
    "#             if zero_count == 1: \n",
    "#                 first_zero_index = i\n",
    "\n",
    "#         print(zero_count)\n",
    "#         if zero_count <= 1:\n",
    "#             return binary\n",
    "#         else:\n",
    "#             return '1'*(first_zero_index + zero_count-1) + '0' +'1'*(len(binary)-first_zero_index-zero_count)\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        zero_count = binary.count(\"0\")  # 0 出现的次数\n",
    "        if zero_count <= 1:\n",
    "            return binary\n",
    "        else:\n",
    "            first_zero_index = binary.index(\"0\")  # 第一个0所在的位置\n",
    "            last_zero_index = first_zero_index + zero_count - 1\n",
    "            return \"1\" * last_zero_index + \"0\" + \"1\" * (len(binary) - last_zero_index - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        ind = 0\n",
    "        while binary and binary[0] == '1':\n",
    "            ind += 1\n",
    "            binary = binary[1:]\n",
    "        cnt = Counter(binary)\n",
    "        return '1' * (ind + max(0, cnt['0']-1)) + ('0' if cnt['0'] > 0 else '') + '1' * cnt['1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        ind = 0\n",
    "        while binary and binary[0] == '1':\n",
    "            ind += 1\n",
    "            binary = binary[1:]\n",
    "        cnt = Counter(binary)\n",
    "        return '1' * (ind + max(0, cnt['0']-1)) + ('0' if cnt['0'] > 0 else '') + '1' * cnt['1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        firstZeroI = 0\n",
    "        while firstZeroI < len(binary):\n",
    "            if binary[firstZeroI] == '0':\n",
    "                break\n",
    "            firstZeroI += 1\n",
    "        if firstZeroI >= len(binary):\n",
    "            return binary\n",
    "        numOnes = sum(int(b == '1') for b in binary[firstZeroI:])\n",
    "        return '1' * firstZeroI + '1' * (len(binary) - firstZeroI - numOnes - 1) + '0' + '1' * numOnes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        left = 0\n",
    "        n = len(binary)\n",
    "        while left < n and binary[left] == '1':\n",
    "            left += 1\n",
    "        right = n - binary[left:].count('1') - 1\n",
    "        if left > right:\n",
    "            return binary\n",
    "        return '1' * right + '0' + '1' * (n - right - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n = len(binary)\n",
    "        count1 = 0\n",
    "        appear0 = False\n",
    "        for i in binary:\n",
    "            if i == '0': appear0 = True\n",
    "            else:\n",
    "                if appear0 == True:\n",
    "                    count1 += 1\n",
    "        if appear0 == True:\n",
    "            return '1' * (n - 1 - count1) + '0' + '1' * count1\n",
    "        else: return binary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        zero_count = 0\n",
    "        first_zero_index = 0\n",
    "        for i in range(len(binary)):\n",
    "            if binary[i] == '0':\n",
    "                zero_count += 1\n",
    "                if zero_count == 1: \n",
    "                    first_zero_index = i\n",
    "\n",
    "        # print(zero_count)\n",
    "        # print(first_zero_index)\n",
    "        # print(binary.count('0'))\n",
    "        # print(binary.index('0'))\n",
    "        if zero_count <= 1:\n",
    "            return binary\n",
    "        else:\n",
    "            return '1'*(first_zero_index + zero_count-1) + '0' +'1'*(len(binary)-first_zero_index-zero_count)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        if '0' not in binary:\n",
    "            return binary\n",
    "        t=binary.index('0')\n",
    "        cnt=binary[t:].count('1')\n",
    "        return '1'*(len(binary)-cnt-1)+'0'+'1'*cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        if '0' not in binary:\n",
    "            return binary\n",
    "        t=binary.index('0')\n",
    "        cnt=binary[t:].count('1')\n",
    "        return '1'*(len(binary)-cnt-1)+'0'+'1'*cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        cnt = 0\n",
    "        flag = False\n",
    "        for char in binary:\n",
    "            if char == '0':\n",
    "                flag = True\n",
    "            elif flag:\n",
    "                cnt += 1\n",
    "        \n",
    "        n = len(binary)\n",
    "\n",
    "        if cnt == 0:\n",
    "            if flag:\n",
    "                return '1' * (n - 1) + '0'\n",
    "            else:\n",
    "                return binary\n",
    "        else:\n",
    "            return '1' * (n - cnt - 1) + '0' + '1' * cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        zeros = binary.count('0')\n",
    "        flag = 0\n",
    "        if zeros == 0 or zeros == 1:\n",
    "            return binary\n",
    "        else:\n",
    "            for i in range(len(binary)):\n",
    "                if binary[i] == '0':\n",
    "                    flag = i\n",
    "                    break\n",
    "\n",
    "            return '1' * (zeros + flag - 1) + '0' + '1'* (len(binary) - flag - zeros)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n = len(binary)\n",
    "        result = \"\"\n",
    "        index = 0\n",
    "        while index < n and binary[index] == '1':\n",
    "            index += 1\n",
    "            result += '1'\n",
    "        t = binary[index:].count('0')\n",
    "\n",
    "        if t < 2:\n",
    "            return binary\n",
    "        else:\n",
    "            result = result + '1' * (t - 1) + '0' + '1' * (n - index - t)\n",
    "            return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        # 先略过前面的‘1’\n",
    "        index = 0\n",
    "        while index < len(binary):\n",
    "            if binary[index] == '1':\n",
    "                index += 1\n",
    "            else:\n",
    "                break \n",
    "        res = ''\n",
    "        res += binary[:index]\n",
    "        count = Counter(binary[index:])\n",
    "        if count['0'] >= 2:\n",
    "            res += (count['0']-1)*'1' + '0' + count['1'] * '1'\n",
    "            return res\n",
    "        else:\n",
    "            return binary\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        i = 0 # 找到第一个0的位置\n",
    "        while i < len(binary):\n",
    "            if binary[i] == '0':\n",
    "                break\n",
    "            i += 1\n",
    "        else: # no break\n",
    "            return binary\n",
    "        # 从i开始的1都移动到最右边\n",
    "        length = len(binary) - i # 剩下的长度\n",
    "        cnt = 0 # 剩下的1的数量\n",
    "        j = i\n",
    "        while j < len(binary):\n",
    "            if binary[j] == '1':\n",
    "                cnt += 1\n",
    "            j += 1\n",
    "        ans = '1' * i + '1' * (length - cnt - 1) + '0' + '1' * cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n = len(binary)\n",
    "        if binary.count('0') < 2:\n",
    "            return binary\n",
    "        else:\n",
    "            n_1 = binary[binary.find('0'):].count('1')\n",
    "            return '1' * (n - n_1 - 1) + '0' + '1' * n_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumBinaryString(self, binary: str) -> str:\r\n",
    "        # 找规律题\r\n",
    "        # 换个思路想 10变01是把1往后挪 如果前面没有0 那么这个挪位没有意义\r\n",
    "        # 此时我们把所有的0都挪到最前面 前面就变为1111110 后面加上1的个数 这样是最大的\r\n",
    "        # 显然这种情况只有 0开头才赚\r\n",
    "        n = len(binary)\r\n",
    "        result =  \"\"\r\n",
    "        index = 0\r\n",
    "        # 找到第一个0开头\r\n",
    "        while index < n and binary[index] == '1':\r\n",
    "            index += 1\r\n",
    "            result += '1'\r\n",
    "        t = binary[index:].count('0')\r\n",
    "        if t < 2:\r\n",
    "            return binary\r\n",
    "        else:\r\n",
    "            return result + '1'*(t-1) + '0' + '1'*(n-index-t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n = len(binary)\n",
    "        cnt = Counter(binary)\n",
    "        if not cnt[\"0\"]:\n",
    "            return binary\n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            if binary[i] == \"0\":\n",
    "                rest_0 = cnt[\"0\"]\n",
    "                rest_1 = cnt[\"1\"]\n",
    "                ans += (rest_0-1)*\"1\" + \"0\" + rest_1*\"1\"\n",
    "                break\n",
    "            else:\n",
    "                ans += \"1\"\n",
    "                cnt[\"1\"] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        #统计0的个数，如果0的个数 <= 1，当前值就是结果\n",
    "        #如果0的个数多于1，将第一个0之外的，全部借助操作2前移。\n",
    "        #将除最后一个0之外的0全部借助操作1替换为1，就是结果\n",
    "        zero_count = binary.count(\"0\")\n",
    "        if zero_count <= 1:\n",
    "            return binary\n",
    "        first_zero_index = binary.index(\"0\")\n",
    "        last_zero_index = first_zero_index + zero_count - 1\n",
    "        # last_zero_index 保持不变，前面全部是1，后面全部是1\n",
    "        res = \"1\" * last_zero_index + \"0\" + \"1\" * (len(binary) - last_zero_index - 1)\n",
    "        #print(res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "\n",
    "        # 找规律题\n",
    "\n",
    "        # 换个思路想 10变01是把1往后挪 如果前面没有0 那么这个挪位没有意义\n",
    "\n",
    "        # 此时我们把所有的0都挪到最前面 前面就变为1111110 后面加上1的个数 这样是最大的\n",
    "\n",
    "        # 显然这种情况只有 0开头才赚\n",
    "\n",
    "        n = len(binary)\n",
    "\n",
    "        result =  \"\"\n",
    "\n",
    "        index = 0\n",
    "\n",
    "        # 找到第一个0开头\n",
    "\n",
    "        while index < n and binary[index] == '1':\n",
    "\n",
    "            index += 1\n",
    "\n",
    "            result += '1'\n",
    "\n",
    "        t = binary[index:].count('0')\n",
    "\n",
    "        if t < 2:\n",
    "\n",
    "            return binary\n",
    "\n",
    "        else:\n",
    "\n",
    "            return result + '1'*(t-1) + '0' + '1'*(n-index-t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n = len(binary)\n",
    "        l = 0\n",
    "        while l < n and binary[l] == '1':\n",
    "            l += 1\n",
    "        cnt0 = binary.count('0')\n",
    "        if cnt0 == 0: return binary\n",
    "        r = binary.find('0')\n",
    "        return '1' * (l + cnt0 - 1) + '0' + '1' * (n - l - cnt0) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        # 10变01是将1向后移\n",
    "        n = len(binary)\n",
    "        res = \"\"\n",
    "        idx = 0\n",
    "        while idx < n and binary[idx] == '1':\n",
    "            idx += 1\n",
    "            res += '1'\n",
    "        t = binary[idx:].count('0')\n",
    "        if t < 2:\n",
    "            return binary\n",
    "        else:\n",
    "            return res + '1' * (t - 1) + '0' + '1' * (n - idx - t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        if '0' not in binary:\n",
    "            return binary\n",
    "        t=binary.index('0')\n",
    "        cnt=binary[t:].count('1')\n",
    "        return '1'*(len(binary)-cnt-1)+'0'+'1'*cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        index = 0\n",
    "        result = \"\"\n",
    "        n = len(binary)\n",
    "        while index < n and binary[index] == '1':\n",
    "            index += 1\n",
    "            result += '1'\n",
    "        cnt = binary[index:].count('0')\n",
    "        if cnt < 2:\n",
    "            return binary\n",
    "        else:\n",
    "            result = result + '1' * (cnt - 1) + '0' + '1' * (n - index - cnt)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        i=0\n",
    "        for i in range(len(binary)):\n",
    "            if binary[i]=='0':\n",
    "                break\n",
    "        a=Counter(binary[i:])\n",
    "\n",
    "        return binary[:i]+(a['0']-1)*'1'+'0'+a['1']*'1' if a['0'] else binary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        \n",
    "        left0 = -1\n",
    "        right0 = -1\n",
    "        for kk in range(len(binary)):\n",
    "            c = binary[kk]\n",
    "            if c=='0':\n",
    "                if left0==-1:\n",
    "                    left0 = kk\n",
    "                else:\n",
    "                    right0 = kk\n",
    "                    break\n",
    "        if (left0==-1) or (right0==-1):\n",
    "            return binary\n",
    "        \n",
    "        C = Counter(binary)\n",
    "        \n",
    "        new_s = '1'*(left0 + C['0']-1) + '0'\n",
    "        new_s = new_s + '1'*(len(binary) - len(new_s))\n",
    "        return new_s\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n = len(binary)\n",
    "        result =  \"\"\n",
    "        index = 0\n",
    "        while index < n and binary[index] == '1':\n",
    "            index += 1\n",
    "            result += '1'\n",
    "        t = binary[index:].count('0')\n",
    "        if t < 2:\n",
    "            return binary\n",
    "        else:\n",
    "            return result + '1'*(t-1) + '0' + '1'*(n-index-t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        # 找规律题\n",
    "        # 换个思路想 10变01是把1往后挪 如果前面没有0 那么这个挪位没有意义\n",
    "        # 此时我们把所有的0都挪到最前面 前面就变为1111110 后面加上1的个数 这样是最大的\n",
    "        # 显然这种情况只有 0开头才赚\n",
    "        n = len(binary)\n",
    "        result =  \"\"\n",
    "        index = 0\n",
    "        # 找到第一个0开头\n",
    "        while index < n and binary[index] == '1':\n",
    "            index += 1\n",
    "            result += '1'\n",
    "        t = binary[index:].count('0')\n",
    "        if t < 2:\n",
    "            return binary\n",
    "        else:\n",
    "            return result + '1'*(t-1) + '0' + '1'*(n-index-t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n, i = len(binary), 0\n",
    "        while i<n and binary[i] == '1': i += 1\n",
    "        if i==n: return binary\n",
    "        while i<n and binary[i] == '0': i += 1\n",
    "        if i==n: return '1' * (n-1) + '0'\n",
    "        return ('0' + binary[i:].count('1') * '1').rjust(n, '1')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        left = 0\n",
    "        binary = list(binary)\n",
    "        while left < len(binary) and binary[left] == '1':\n",
    "            left += 1\n",
    "        right = left + 1\n",
    "        while right < len(binary):\n",
    "            if binary[right] == '1':\n",
    "                right += 1\n",
    "                continue\n",
    "            if right - left == 1:\n",
    "                binary[left] = '1'\n",
    "            else:\n",
    "                binary[left] = '1'\n",
    "                binary[right] = '1'\n",
    "                binary[left + 1] = '0'\n",
    "            left += 1\n",
    "            right += 1\n",
    "        return ''.join(binary)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n = len(binary)\n",
    "        zeros = 0\n",
    "        idx = None\n",
    "        for i in range(n):\n",
    "            if(binary[i] == '0'):\n",
    "                zeros += 1\n",
    "                if(idx == None):\n",
    "                    idx = i \n",
    "        result = ['1']*n \n",
    "        if(idx != None):\n",
    "            result[idx+zeros-1] = '0'\n",
    "        return ''.join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n = len(binary)\n",
    "        zeros = 0\n",
    "        idx = None\n",
    "        for i in range(n):\n",
    "            if(binary[i] == '0'):\n",
    "                zeros += 1\n",
    "                if(idx == None):\n",
    "                    idx = i \n",
    "        result = ['1']*n \n",
    "        if(idx != None):\n",
    "            result[idx+zeros-1] = '0'\n",
    "        return ''.join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        prefix = 0\n",
    "        for i in binary:\n",
    "            if i == \"0\":\n",
    "                break\n",
    "            prefix += 1\n",
    "        count = binary.count(\"1\")\n",
    "        if count == len(binary):\n",
    "            return binary\n",
    "        ans = [\"1\"] * len(binary)\n",
    "        ans[-(count - prefix + 1)] = \"0\"\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n = len(binary)\n",
    "        if '0' not in binary:\n",
    "            return binary\n",
    "        else:\n",
    "            cnt0 = binary.count('0')\n",
    "            for i,c in enumerate(binary):\n",
    "                if c == '0':\n",
    "                    index = i\n",
    "                    break\n",
    "            res = ['1']*n\n",
    "            res[index+cnt0-1] = '0'\n",
    "            return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        flag = True\n",
    "        binary_list = list(binary)\n",
    "\n",
    "        # Iterate through the binary string to count '1's and update the flag\n",
    "        for c in binary:\n",
    "            flag = flag and c == '1'\n",
    "            left += flag and c == '1'\n",
    "            right += (not flag) and c == '1'\n",
    "\n",
    "        # Check if there is room for transformation\n",
    "        if left + right < len(binary) - 1:\n",
    "            k = len(binary) - right - 1\n",
    "\n",
    "            # Update the binary list to form the maximum binary string\n",
    "            for i in range(len(binary)):\n",
    "                binary_list[i] = '0' if i == k else '1'\n",
    "\n",
    "        # Convert the list back to a string and return it\n",
    "        return ''.join(binary_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n = len(binary)\n",
    "        if '0' not in binary:\n",
    "            return binary\n",
    "        else:\n",
    "            cnt0 = binary.count('0')\n",
    "            index = binary.index('0')\n",
    "            res = ['1']*n\n",
    "            res[index+cnt0-1] = '0'\n",
    "            return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        n = len(binary)\n",
    "        zeros = 0\n",
    "        idx = None\n",
    "        for i in range(n):\n",
    "            if(binary[i] == '0'):\n",
    "                zeros += 1\n",
    "                if(idx == None):\n",
    "                    idx = i \n",
    "        result = ['1']*n \n",
    "        if(idx != None):\n",
    "            result[idx+zeros-1] = '0'\n",
    "        return ''.join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        f = True\n",
    "        for c in binary:\n",
    "            f = f and c=='1'\n",
    "            if f:\n",
    "                left += 1\n",
    "            elif c=='1':\n",
    "                right += 1\n",
    "        res = [binary[i] for i in range(len(binary))]\n",
    "        if left+right<len(binary)-1:\n",
    "            k = len(binary)-right-1\n",
    "            for i in range(len(binary)-1,-1,-1):\n",
    "                res[i] = '0' if (i==k) else '1'\n",
    "        return ''.join(res) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        left, right, flag = 0, 0, True\n",
    "        ans = [c for c in binary]\n",
    "        for c in binary:\n",
    "            flag = flag and c == '1'\n",
    "            left += flag and c == '1'\n",
    "            right += not flag and c == '1'\n",
    "        n = len(binary)\n",
    "        if left + right < n - 1:\n",
    "            k = n - right - 1\n",
    "            for i in range(n):\n",
    "                ans[i] = '0' if i == k else '1'\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBinaryString(self, binary: str) -> str:\n",
    "        # 首先可以确定的是，只有第二位是0的时候才能发生变化\n",
    "        # 从贪心的角度，肯定是希望高位尽可能是1的\n",
    "        # 连续的零可以变成 1...10， 所以希望前面又更多的零\n",
    "        # 应该是两次遍历就能解决问题\n",
    "        if '0' not in binary:\n",
    "            return binary\n",
    "        binary = list(binary)\n",
    "        idx = binary.index('0')\n",
    "        binary = binary[idx:]\n",
    "        n1 = binary.count('0')\n",
    "        n2 = binary.count('1')\n",
    "        return '1'*idx + '1' * (n1-1) + '0' + '1' * n2\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
